package classical_problems_150;

import java.util.ArrayList;
import java.util.List;

public class P_0015 {

    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private void quick_sort_3(int[] nums, int left, int right){
        if(right<=left) return;
        int pivot = nums[left];
        int i = left;
        int lt = left, gt = right; // [left, lt-1]  [gt+1, right]
        while(i<=gt){
            if(nums[i]<pivot){
                swap(nums, i, lt);
                i++;
                lt++;
            } else if (nums[i] > pivot){
                swap(nums, i, gt);
                gt--;
            } else i++;
        }
        quick_sort_3(nums, left, lt-1);
        quick_sort_3(nums, gt+1, right);
    }

    private int binarySearch(int[] nums, int left, int right, int target){
        while(right >= left){
            int mid = (left + right) / 2;
            if(nums[mid]>target){
                right = mid-1;
            } else if (nums[mid] < target){
                left = mid + 1;
            } else return mid;
        }
        return -1;
    }

    public List<List<Integer>> threeSum(int[] nums) {
        quick_sort_3(nums, 0, nums.length-1);
        List<List<Integer>> res = new ArrayList<>();
        for(int i=0; i<nums.length-2; i++){
            for(int j=i+1; j<nums.length-1; j++){
                // 重复的元素会导致重复的三元组
                if(j>i+1 && nums[j] == nums[j-1]) continue;
                int target = -(nums[i] + nums[j]);
                int target_index = this.binarySearch(nums, j+1, nums.length-1, target);
                if(target_index>=0){
                    if(! res.isEmpty()){
                        List<Integer> last_arr = res.getLast();
                        if(last_arr.get(0) >= nums[i] && last_arr.get(1) >= nums[j]) continue;
                    }
                    List<Integer> arr = new ArrayList<>();
                    arr.add(nums[i]);
                    arr.add(nums[j]);
                    arr.add(nums[target_index]);
                    res.add(arr);
                }

            }
        }
        return res;
    }

    public static void main(String[] args){
        P_0015 solution = new P_0015();
        int[] arr = {-1,0,1,2,-1,-4};
        solution.threeSum(arr);

    }
}
